import java.util.Random;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: lenovo
 * Date: 2023 -05 -06
 * Time: 21:57
 */
public class Sort {
    public static void InsertionSorting(int[] array){
        for (int i = 1; i < array.length ; i++) {
            int tmp=array[i];
            int j = i-1;
            for (j = i-1; j >=0 ; j--) {
                if(array[j]>tmp){
                    array[j+1]=array[j];
                    array[j]=tmp;
                }else{
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }
    public static void shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int tmp=array[i];
            int j = i-gap;
            for (j = i-gap; j >=0 ; j-=gap) {
                if(array[j]>tmp){
                    array[j+gap]=array[j];
                    array[j]=tmp;
                }else{
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }
    public static void shellSort(int[] array){
        int gap=array.length;
        while(gap>1){
            gap/=2;
            shell(array,gap);
        }
    }
    public static int[] randomArray(){
        int[] ret=new int[1000000];
        Random random=new Random();
        for (int i = 0; i < ret.length; i++) {
            ret[i]=random.nextInt(1000000);
        }
        return ret;
    }
    public static void testInsertionSorting(int[] array){
        long startTime=System.currentTimeMillis();
        InsertionSorting(array);
        long endTime=System.currentTimeMillis();
        System.out.println("插入排序所需要的时间:"+(endTime-startTime));
    }
    public static void testShellSort(int[] array){
        long startTime=System.currentTimeMillis();
        shellSort(array);
        long endTime=System.currentTimeMillis();
        System.out.println("希尔排序所需要的时间:"+(endTime-startTime));
    }
    public static void main(String[] args) {
        int[] array=randomArray();
        int[] array2=randomArray();
        testInsertionSorting(array);
        testShellSort(array2);

    }
}
